#include "common.hpp"

struct SNode
{
    int data;
    SNode *next = NULL;
};

class LinkTable
{
public:
    SNode *head = NULL;
    SNode *rear = NULL;

    LinkTable()
    {
        // head仅在构造函数初始化,仅在析构函数中被释放,不存数据,这样确保在使用过程中不用担心head为空指针
        head = new SNode();
        head->next = NULL;
        rear = head;
    }

    virtual ~LinkTable()
    {
        ClearAll();
        if (head)
        {
            // 验证此时head就是rear
            assert(head == rear);
            rear = NULL;
            delete head;
            head = NULL;
            printf("release head\n");
        }
    }

    void ClearAll()
    {
        while (Delete(head, head->next))
        {
        }
    }

    void Insert(const std::vector<int> &set)
    {
        for (auto iter = set.begin(); iter < set.end(); iter++)
        {
            SNode *node = new SNode();
            node->data = *iter;
            rear->next = node;
            rear = node;
        }
        rear->next = NULL;
    }

    bool Delete(SNode *prev, SNode *curr)
    {
        if (curr == NULL || prev == NULL)
            return false;
        printf("\ndelete ");
        if (curr->next == NULL)
        {
            // 删除尾节点
            printf("%d", curr->data);
            delete curr;
            prev->next = NULL;
            rear = prev;
        }
        else
        {
            printf("%d", curr->data);
            auto *temp = curr->next;
            delete curr;
            prev->next = temp;
        }
        return true;
    }

    void Print()
    {
        auto *curr = head->next;
        while (curr)
        {
            printf("%d ", curr->data);
            curr = curr->next;
        }
        printf("\n");
    }

    bool InsertBehind(int tag, int data)
    {
        auto *res = Find(tag);
        if (res == NULL)
            return false;
        auto *temp = new SNode();
        temp->data = data;
        if (res->next == NULL)
        {
            assert(res == rear);
            // 目标节点为尾节点
            res->next = temp;
            temp->next = NULL;
            rear = temp;
        }
        else
        {
            auto *next = res->next;
            res->next = temp;
            temp->next = next;
        }
        return true;
    }

    SNode *Find(int tag)
    {
        SNode *curr = head->next;
        while (curr != NULL)
        {
            if (curr->data == tag)
            {
                break;
            }
            else if (curr->next == NULL)
            {
                // 遍历完所有节点仍没有匹配到
                assert(curr == rear);
                curr = NULL;
                break;
            }
            else
            {
                curr = curr->next;
            }
        }
        return curr;
    }
};

int main(int argc, char **argv)
{
    LinkTable table;
    std::vector<int> datas{2, 6, 3, 5, 7, 9, 0, 1};
    std::sort(datas.begin(), datas.end());
    Print(datas);
    table.Insert(datas);
    table.Print();
    table.InsertBehind(5, 88);
    table.InsertBehind(88, 99);
    table.Print();
    table.ClearAll();
    table.Print();
    return 0;
}